『AGC 023F』01 on Tree

Problem

Time limit : 2sec / Memory limit : 256MB

题意简述：给你一棵由$0$和$1$组成的树（就是每个点的权值为$0$或者$1$），让你求该树的一种排列，使得每个节点的孩子都排在这个节点的后面，并且逆序对数量最小。

door♂

Solution

把序列看成若干个集合的并

对于一个集合$C$记$C_0,C_1$为集合中$0,1$出现的次数

则我们考虑何时应该把这个集合$u$接在它父亲$p$的$01$集合后面

考虑如何选择这个集合$u$

我们知道，对于两个集合$m,n$，如果要使$m$放在$n$前面更优的话，必然满足$m_0 > n_0, m_1 < n_1$。然后把这两个不等式左右两边都比一下，容易得到需要满足$\dfrac{m_0}{m_1} > \dfrac{n_0}{n_1}$

所以对于一个节点$u$，我们存储它的集合信息为$u_0,u_1$，因为只需要知道这两个东西就可以比较它们的偏序

于是我们就维护一个堆或者一个set，用来每次弹出最大的$\dfrac{u_0}{u_1}$的$u$，接在它的父亲节点的后面，然后把父亲节点和这个节点用一个并查集缩起来，相当于一个点

不停地取元素，直到堆为空。时间复杂度$O(\alpha n\log n)$，其中$\alpha$可以近似认为是一个常数。

Code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#define MAXN 200010
using namespace std;
typedef long long ll;
int N;
ll A[MAXN];
map <ll, int> M;
inline void _read(int &x)
{
	x = 0;
	register int y = 1;
	char t = getchar();
	while (!isdigit(t) && t != '-') t = getchar();
	if (t == '-')
	{
		y = -1;
		t = getchar();
	}
	while (isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar();
	}
	x *= y;
}
inline void _read(ll &x)
{
	x = 0;
	register ll y = 1;
	char t = getchar();
	while (!isdigit(t) && t != '-') t = getchar();
	if (t == '-')
	{
		y = -1;
		t = getchar();
	}
	while (isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar();
	}
	x *= y;
}
int main()
{
	_read(N);
	for (int i = 1; i <= N; ++i) _read(A[i]);
	M[0] = 1;
	ll ans = 0;
	for (int i = 1; i <= N; ++i)
	{
		A[i] += A[i - 1];
		ans += M[A[i]];
		M[A[i]] += 1;
	}
	printf("%lld\n", ans);
	return 0;
}